from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        temp = [m for m in nums]
        result = []

        def dfs(x):
            if x == len(nums) - 1:
                result.append(list(temp))
                return
            t = set()
            for i in range(x, len(temp)):
                # 用去元素重复时剪枝
                if temp[i] in t:
                    continue
                t.add(temp[i])
                temp[i], temp[x] = temp[x], temp[i]
                dfs(x + 1)
                temp[i], temp[x] = temp[x], temp[i]

        dfs(0)
        return result


if __name__ == '__main__':
    x = Solution()
    print(x.permute([1, 2, 3]))
